package bintree.leetcode;

public class Num105 {
        private int index = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
           return buildTree(preorder, inorder,0,inorder.length-1);
        }

    private TreeNode buildTree(int[] preorder, int[] inorder, int left, int right) {
            if (left>right){
                //【2，1）空区间
                return null;
            }
            if (index == preorder.length){
                //前序遍历的元素己经处理完毕，没有新节点
                return null;
            }
            TreeNode root = new TreeNode(preorder[index]);
            index++;
            int pos = find(root.val,inorder);
            root.left=buildTree(preorder,inorder,left,pos-1);
            root.right=buildTree(preorder,inorder,pos+1,right);
            return root;
    }

    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
}
